package j2024.j202411;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class j1126 {

    /**
     * 433. 最小基因变化
     * 基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
     *
     * 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。
     * 一次基因变化就意味着这个基因序列中的一个字符发生了变化。
     *
     * 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
     * 另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。
     * （变化后的基因必须位于基因库 bank 中）
     *
     * 给你两个基因序列 start 和 end ，以及一个基因库 bank ，
     * 请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
     *
     * 注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
     * @param startGene
     * @param endGene
     * @param bank
     * @return
     */

    public int minMutation(String startGene, String endGene, String[] bank) {
        HashSet<String> vis = new HashSet<>();
        HashSet<String> ban = new HashSet<>();
        char[] change = {'A','C','G','T'};
        for(String i:bank){
            ban.add(i);
        }
        if(startGene.compareTo(endGene)==0){
            return 0;
        }
        if(!ban.contains(endGene)){
            return -1;
        }
        Queue<String> q = new LinkedList<>();
        q.add(startGene);
        vis.add(startGene);
        int step = 0;
        while(!q.isEmpty()){
            step++;
            int sz = q.size();
            while(sz--!=0){
                String t = q.poll();
                for (int i = 0; i < 8; i++) {
                    char[] s = t.toCharArray();
                    for (int j = 0; j < 4; j++) {
                        s[i] = change[j];
                        String a = new String(s);
                        if(ban.contains(a) && !vis.contains(a)){
                            if(a.compareTo(endGene)==0){
                                return step;
                            }
                            q.add(a);
                            vis.add(a);
                        }
                    }
                }
            }
        }
        return -1;
    }
}
